The present invention relates generally to the field of computers and computer systems. More particularly, the present invention relates to a cache line replacement policy to avoid memory page thrashing.
Since the beginning of computing, processors have been faster than memories. Even though memory technology has evolved and improved over time, so has processor technology. What this means is that processors often have to remain idle for substantial amounts of time while waiting for the memory to respond to a memory request. As a result, system performance can be negatively impacted.
Computer systems have evolved to include memory hierarchies comprising various types of long term storage, main memory, and caches. However, as one moves down the down the memory hierarchy from caches to long term storage, device access times increase dramatically. An ideal solution is to have enough cache memory or fast main memory available to service the currently executing program. But in most systems, such memory is present in only limited amounts or the program demands more memory than is available.
Caches are generally used to keep often used or recently used data close to or within the processor. The idea is that by storing recently used data in close proximity to the processor, the next time a memory request is made for that particular data, a long memory access to main memory or the hard disk drive is not necessary. When a computer starts up, the cache is empty. But over time, the cache continues to fill up until there are no longer any empty entries for new data. This is not a problem as long as invalid entries are available for replacement. But if all existing entries are valid, the cache replacement logic must delete valid entries to make room for incoming data.
In an efficiently designed computer system, the chipset needs to return requested data to the processor with minimum latency in order to provide maximum system performance. A number of factors can influence this latency, including overall system loading and the memory technology deployed. One factor that can become significant is the specific interaction between transactions that are closely related by the time that they are issued to the processor bus. When these transactions cause a conflict or xe2x80x9cpage missxe2x80x9d in the memory system, read latency seen by the processor can increase dramatically. The impact of these conflicts is often minimized by the inherent randomness of transaction requests. However, certain application access patterns can cause pathological cases where every access is impacted by these page miss cases.
Some of these conflicts are inevitable, as operating system, application, and chipset design details can interact in ways to create vicious cases. On the other hand, a substantial class of conflicts can arise simply from an interaction between the way in which memory controllers are designed and the way in which processor caches are designed. These conflicts can have a significant impact on processor and overall system performance.